import java.time.ZonedDateTime;
import java.util.*;

import static javax.management.Query.and;
import static javax.management.Query.between;

class cmp implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
}

public class Recursion {
    public static void main(String[] args) {

        int[][] indexs = new int[9][9];
        int index = 0;
        for(int y = 0; y < 3; y++){
            for(int x = 0; x < 3; x++){
                for(int i = 3 * y; i < 3 * y + 3; i++){
                    for(int j = 3 * x; j < 3 * x + 3; j++){
                        indexs[i][j] = index;
                    }
                }
                index++;
            }
        }

        List<String> list = new ArrayList<String>();
        boolean a = true;
        boolean b = true;
        System.out.println(a || b);
        List<StringBuilder> s = new LinkedList<>();
        String ss = ":ss";
        (new StringBuilder(ss)).delete(ss.length() - 1, ss.length());
        boolean[] bs = new boolean[2];
        System.out.println(bs[0]);
        List<Integer> path = new LinkedList<>();
        System.out.println(0 ^ 5 ^ 5);
        StringBuilder sss = new StringBuilder();
//        sss.delete(sss.length() - 1, ss.length());
        Set<String> set = new HashSet<String>();
        List<String> listl = List.of("11","22","33");
        listl.clear();
        System.out.println(listl.toString());
        ZonedDateTime zdt = ZonedDateTime.now();
        System.out.println(zdt);
        List<Integer> l = new ArrayList<>(List.of(4, 5, 1, 2, 3, 6, 7, 8, 9));
        System.out.println(l.hashCode());
        l.sort((x,y)-> x-y);
        System.out.println(l.hashCode());
        System.out.println(l);
        System.out.println(List.of(4, 5, 1, 2, 3, 6, 7, 8, 9).hashCode());
        String[] c = {"aa","bb","cc"};
        System.out.println(c.toString());
        System.out.println(Arrays.toString(c));
        StringBuilder s1 = new StringBuilder("1111");
        System.out.println(s1.toString());
        System.out.println(s1);
        s1.setCharAt(0,'q');
//        Character.isDigit()
        System.out.println(s1.toString());
    }



    /**
     * 不同路劲III Unique diff
     */

    int mUnique, nUnique, count0Unique;
    int startxUnique, startyUnique;
    int retUnique;
    int[][] gridUnique;
    int[] dyUnique = {-1, 1, 0, 0};
    int[] dxUnique = {0, 0, -1, 1};
    boolean[][] checkUnique;
    public int uniquePathsIII(int[][] _grid) {
        gridUnique = _grid;
        mUnique = grid.length;
        nUnique = grid[0].length; retUnique = 0;
        check = new boolean[mUnique][nUnique];
        for(int y = 0; y < mUnique; y++){
            for(int x = 0; x < nUnique; x++){
                int v = grid[y][x];
                if(v == 0) count0Unique++;
                else if(v == 1) {
                    startxUnique = x; startyUnique = y;
                }
            }
        }

        recursionUnique(startyUnique, startxUnique, -1);

        return retUnique;
    }

    void recursionUnique(int y, int x, int count){
        if(grid[y][x] == 2){
            if(count == count0Unique) retUnique++;
            return;
        }

        for(int i = 0; i < 4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy < 0 || yy == mUnique || xx < 0 || xx == nUnique || check[yy][xx] || grid[yy][xx] == -1){
                continue;
            }

            check[y][x] = true;

            recursion(yy, xx, count + 1);

            check[y][x] = false;
        }
    }

    /**
     * 黄金矿工
     */

    boolean[][] check;
    int mMaximumGold, nMaximumGold, pathMaximumGold, retMaximumGold;
    int[] dx; int[] dy;
    int[][] grid;
    public int getMaximumGold(int[][] _grid) {
        grid = _grid;
        mMaximumGold = grid.length; nMaximumGold = grid[0].length;

        dx = new int[]{0, 0, -1, 1};
        dy = new int[]{-1, 1, 0, 0};
        for(int y = 0; y < mMaximumGold; y++){
            for(int x = 0; x < nMaximumGold; x++){
                if(grid[y][x] == 0) continue;
                check = new boolean[mMaximumGold][nMaximumGold];
                pathMaximumGold = 0;
                recursion(y, x);
            }
        }
        return retMaximumGold;
    }

    void recursion(int y, int x){
        if(grid[y][x] == 0){
            retMaximumGold = Math.max(retMaximumGold, pathMaximumGold);
            return;
        }

        for(int i = 0; i < 4; i++){

            int xx = x + dx[i];
            int yy = y + dy[i];

            if(yy < 0 || yy ==  mMaximumGold || xx < 0 || xx == nMaximumGold || check[yy][xx]) {
                retMaximumGold = Math.max(retMaximumGold, pathMaximumGold + grid[y][x]);
                continue;
            }

            pathMaximumGold += grid[y][x];
            retMaximumGold = Math.max(retMaximumGold, pathMaximumGold);

            check[y][x] = true;

            recursion(yy, xx);

            pathMaximumGold -= grid[y][x];
            check[y][x] = false;
        }
    }
    /**
     * 单词搜索
     */
    boolean[][] pathExist;
    int mExist, nExist, lenExist;
    char[] wordExist;
    char[][] boardExist;
    public boolean exist(char[][] _board, String _word) {
        boardExist = _board; wordExist = _word.toCharArray();
        lenExist = wordExist.length;
        mExist = boardExist.length; nExist = boardExist[0].length;
        for(int y = 0; y < mExist; y++){
            for(int x = 0; x < nExist; x++){
                if(wordExist[0] == boardExist[y][x]){
                    pathExist = new boolean[mExist][nExist];
                    if(recursionExist(y, x, 0)) return true;
                }
            }
        }
        return false;
    }

    boolean recursionExist(int y, int x, int index){
        if(y >= mExist || x >= nExist || y < 0 || x < 0) return false;

        char c = boardExist[y][x];

        if(c == wordExist[index] && !pathExist[y][x]){
            if(index == lenExist - 1){
                return true;
            }

            //上
            pathExist[y][x] = true;
            if(recursionExist(y - 1, x, index + 1)) return true;
            pathExist[y][x] = false;

            //下
            pathExist[y][x] = true;
            if(recursionExist(y + 1, x, index + 1)) return true;
            pathExist[y][x] = false;
            //左
            pathExist[y][x] = true;
            if(recursionExist(y, x - 1, index + 1)) return true;
            pathExist[y][x] = false;
            //右
            pathExist[y][x] = true;
            if(recursionExist(y, x + 1, index + 1)) return true;
            pathExist[y][x] = false;
        }
        return false;
    }

    /**
     * 有效的数独
     */
    public boolean isValidSudokuBe(char[][] board) {
        boolean[][] row = new boolean[9][10];
        boolean[][] col = new boolean[9][10];
        boolean[][][] block = new boolean[3][3][10];

        for(int y = 0; y < 9; y++){
            for(int x = 0; x < 9; x++){
                if(!Character.isDigit(board[y][x])) continue;

                int v = board[y][x] - '0';

                if(!row[x][v] && !col[y][v] && !block[y/3][x/3][v]){
                    row[x][v] = true;
                    col[y][v] = true;
                    block[y/3][x/3][v] = true;
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    //暴力解法
    public boolean isValidSudoku(char[][] board) {
        LinkedList<Set<Integer>> row = new LinkedList<>();
        LinkedList<Set<Integer>> col = new LinkedList<>();
        LinkedList<Set<Integer>> block = new LinkedList<>();
        int[][] indexs = new int[9][9];
        int index = 0;
        for(int y = 0; y < 3; y++){
            for(int x = 0; x < 3; x++){
                for(int i = 3 * y; i < 3 * y + 3; i++){
                    for(int j = 3 * x; j < 3 * x + 3; j++){
                        indexs[i][j] = index;
                    }
                }
                index++;
            }
        }

        for(int i = 0; i < 9; i++){
            row.add(new HashSet<>());
            col.add(new HashSet<>());
            block.add(new HashSet<>());
        }

        for(int y = 0; y < 9; y++){
            for(int x = 0; x < 9; x++){
                if(!Character.isDigit(board[y][x])) continue;

                int v = board[y][x] - '0';

                Set<Integer> b = block.get(indexs[y][x]);
                Set<Integer> xx = row.get(x);
                Set<Integer> yy = col.get(y);

                if(!xx.contains(v) && !yy.contains(v) && !b.contains(v)){
                    xx.add(v);
                    yy.add(v);
                    b.add(v);
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * n皇后  SolveNQueens
     */
    boolean[] rowSolveNQueens;
    boolean[] angles1SolveNQueens;
    boolean[] angles2SolveNQueens;
    int nSolveNQueens;
    List<List<String>> retSolveNQueens;
    List<String> pathSolveNQueens;
    StringBuilder strSolveNQueens;
    public List<List<String>> solveNQueens(int _n) {
        nSolveNQueens = _n;
        rowSolveNQueens = new boolean[nSolveNQueens + 1];
        angles1SolveNQueens = new boolean[nSolveNQueens * 2];
        angles2SolveNQueens = new boolean[nSolveNQueens * 2];
        retSolveNQueens = new LinkedList<>();
        pathSolveNQueens = new LinkedList<>();
        strSolveNQueens = new StringBuilder();
        for(int i = 0; i < nSolveNQueens; i++){
            strSolveNQueens.append(".");
        }
        recursionSolveNQueens(0);
        return retSolveNQueens;
    }

    void recursionSolveNQueens(int y){
        if(y == nSolveNQueens){
            retSolveNQueens.add(new LinkedList<>(pathSolveNQueens));
            return;
        }

        StringBuilder str1 = new StringBuilder(strSolveNQueens);
        for(int x = 0; x < nSolveNQueens; x++){
            if(rowSolveNQueens[x] || angles1SolveNQueens[y - x + nSolveNQueens] || angles2SolveNQueens[y + x]){
                continue;
            }

            str1.setCharAt(x, 'Q');

            rowSolveNQueens[x] = angles1SolveNQueens[y - x + nSolveNQueens] = angles2SolveNQueens[y + x] = true;

            pathSolveNQueens.add(str1.toString());

            recursion(y + 1);

            pathSolveNQueens.remove(pathSolveNQueens.size() - 1);

            rowSolveNQueens[x] = angles1SolveNQueens[y - x + nSolveNQueens] = angles2SolveNQueens[y + x] = false;

            str1.setCharAt(x, '.');
        }
    }

    /**
     * 优美的排列
     */
    int retCountArrangement;
    int nCountArrangement;
    boolean[] checkCountArrangement;
    public int countArrangement(int _n) {
        nCountArrangement = _n;
        checkCountArrangement = new boolean[nCountArrangement + 1];
        recursion(1);
        return retCountArrangement;
    }

    void recursionCountArrangement(int index){
        if(index == nCountArrangement + 1){
            retCountArrangement++;
            return;
        }

        for(int v = 1; v <= nCountArrangement; v++){
            if(checkCountArrangement[v]) continue;
            if(index % v == 0 || v % index == 0){
                checkCountArrangement[v] = true;
                recursion(index + 1);
                checkCountArrangement[v] = false;
            }
        }
    }

    /**
     *  字母大小写全排列
     */
    StringBuilder pathLetterCase;
    char[] sLetterCase;
    List<String> retLetterCase;
    int nLetterCase;
    public List<String> letterCasePermutation(String _s) {
        pathLetterCase = new StringBuilder();
        sLetterCase = _s.toCharArray();
        retLetterCase = new LinkedList<>();
        nLetterCase = _s.length();
        recursion(0);
        return retLetterCase;
    }

    void recursionLetterCasePermutation(int i){
        if(i == nLetterCase){
            retLetterCase.add((new StringBuilder(pathLetterCase)).toString());
            return;
        }

        if(Character.isDigit(sLetterCase[i])) {
            pathLetterCase.append(sLetterCase[i]);
            recursion(i+1);
            pathLetterCase.delete(pathLetterCase.length() - 1, pathLetterCase.length());
            return;
        }

        pathLetterCase.append(Character.toLowerCase(sLetterCase[i]));
        recursionLetterCasePermutation(i+1);
        pathLetterCase.delete(pathLetterCase.length() - 1, pathLetterCase.length());

        pathLetterCase.append(Character.toUpperCase(sLetterCase[i]));
        recursionLetterCasePermutation(i+1);
        pathLetterCase.delete(pathLetterCase.length() - 1, pathLetterCase.length());
    }

    /**
     * 组合总和
     */
    List<List<Integer>> retCombinationSum;
    List<Integer> pathCombinationSum;
    int[] candidates;
    boolean[] checkCombinationSum;
    int target, nCandidates;
    Set<Integer> combinationSet;
    public List<List<Integer>> combinationSum(int[] _candidates, int _target) {
        retCombinationSum = new ArrayList<>();
        pathCombinationSum = new ArrayList<>();
        target = _target;
        nCandidates = _candidates.length;
        candidates = _candidates;
        recuresion(0, 0);
        return retCombinationSum;
    }

    void recuresion(int sum,int s){
        if(sum > target) return;
        if(sum == target){
            retCombinationSum.add(new ArrayList<>(pathCombinationSum));
            return;
        }

        for(int i = s; i < nCandidates; i++){
            pathCombinationSum.add(candidates[i]);
            recuresion(sum+candidates[i], i);
            pathCombinationSum.remove(pathCombinationSum.size()-1);
        }
    }
    void recuresion(int sum){
        if(sum > target) return;
        if(sum == target){
            //使用排序的hash值来实现去重
            List<Integer> path1 = new ArrayList<>(pathCombinationSum);
            path1.sort((x, y) -> x - y);
            int code = path1.hashCode();
            if(combinationSet.contains(code)){
                return;
            }
            combinationSet.add(code);
            retCombinationSum.add(path1);
            return;
        }

        for(int i = 0; i < nCandidates; i++){
            pathCombinationSum.add(candidates[i]);
            recuresion(sum+candidates[i]);
            pathCombinationSum.remove(pathCombinationSum.size()-1);
        }
    }

    /**
     * 目标和
     */
    int pathFindTargetSumWays, retFindTargetSumWays, targetFindTargetSumWays, nFindTargetSumWays;
    int[] numsFindTargetSumWays;
    public int findTargetSumWays(int[] _nums, int _target) {
        pathFindTargetSumWays = 0;retFindTargetSumWays = 0;
        nFindTargetSumWays = _nums.length;numsFindTargetSumWays = _nums;
        targetFindTargetSumWays = _target;
        recursion(0);
        return retFindTargetSumWays;
    }

    void recursion(int i){
        if(i == nFindTargetSumWays){
            if(pathFindTargetSumWays == targetFindTargetSumWays) retFindTargetSumWays++;
            return;
        }
        pathFindTargetSumWays += numsFindTargetSumWays[i];

        recursion(i + 1);
        pathFindTargetSumWays -= numsFindTargetSumWays[i];

        pathFindTargetSumWays -= numsFindTargetSumWays[i];

        recursion(i + 1);
        pathFindTargetSumWays += numsFindTargetSumWays[i];
    }
    /**
     * 组合
     */
    List<Integer> combinePath;
    List<List<Integer>> combineRet;
    public List<List<Integer>> combine(int n, int k) {
        combineRet = new LinkedList<>();
        combinePath = new LinkedList<>();
        recursion(n, k, 1);
        return combineRet;
    }

    void recursion(int n, int k, int s){
        if(combinePath.size() == k){
            combineRet.add(new LinkedList<>(combinePath));
            return;
        }

        for(int i = s; i <= n; i++){
            combinePath.add(i);
            recursion(n, k, i + 1);
            combinePath.remove(combinePath.size() - 1);
        }
    }
    /**
     * 括号生成
     */
    List<String> retParenthesis;
    int stackParenthesis;
    StringBuilder pathParenthesis;
    public List<String> generateParenthesis(int n) {
        retParenthesis = new LinkedList<>();
        stackParenthesis = 0;
        pathParenthesis = new StringBuilder();
        dfsParenthesis(n, n);
        return retParenthesis;
    }

    void dfsParenthesis(int n1, int n2){
        if(n1 == 0){
            StringBuilder s = new StringBuilder(pathParenthesis);
            for(int i = 0; i < n2; i++){
                s.append(")");
            }
            retParenthesis.add(s.toString());
            return;
        }

        //选择（
        pathParenthesis.append("(");
        stackParenthesis += 1;

        dfsParenthesis(n1 - 1, n2);

        pathParenthesis.delete(pathParenthesis.length() - 1, pathParenthesis.length());
        stackParenthesis -= 1;

        // 选择)
        if(stackParenthesis != 0){
            pathParenthesis.append(")");
            stackParenthesis -= 1;

            dfsParenthesis(n1, n2 - 1);

            pathParenthesis.delete(pathParenthesis.length() - 1, pathParenthesis.length());
            stackParenthesis += 1;
        }
    }
    /**
     * 全排列 II
     * 还可以通过排序
     */
    List<Integer> pathPermuteUnique;
    List<List<Integer>> retPermuteUnique;
    boolean[] checkPermuteUnique;
    int nPermuteUnique;
    public List<List<Integer>> permuteUnique(int[] nums) {
        pathPermuteUnique = new LinkedList<>();
        retPermuteUnique = new LinkedList<>();
        nPermuteUnique = nums.length;
        checkPermuteUnique = new boolean[nPermuteUnique];
        dfsPermuteUnique(nums);
        return retPermuteUnique;
    }

    void dfsPermuteUnique(int[] nums){
        if(pathPermuteUnique.size() == nPermuteUnique){
            retPermuteUnique.add(new LinkedList(pathPermuteUnique));
            return;
        }

        boolean[] check1 = new boolean[21];
        for(int i = 0; i < nPermuteUnique; i++){
            if(checkPermuteUnique[i] || check1[nums[i]+10]) continue;
            pathPermuteUnique.add(nums[i]);
            checkPermuteUnique[i] = true;
            check1[nums[i]+10] = true;
            dfsPermuteUnique(nums);
            pathPermuteUnique.remove(pathPermuteUnique.size() - 1);
            checkPermuteUnique[i] = false;
        }
    }

    /**
     * 电话号码的字母组合
     */
    String[] numChar = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> retDigits;
    int nDigits;
    public List<String> letterCombinations(String digits) {
        nDigits = digits.length();
        retDigits = new LinkedList<>();
        char[] chars = digits.toCharArray();
        dfs(chars, 0, new StringBuilder());
        return retDigits;
    }

    void dfs(char[] chars, int i, StringBuilder s){

        if(i == nDigits){
            if(s.length() == 0) return;
            retDigits.add(new String(s.toString()));
            return;
        }
        String tmp = numChar[chars[i] - '0'];

        for(int j = 0; j < tmp.length(); j++){
            s.append(tmp.charAt(j));
            dfs(chars, i + 1, s);
            s.delete(s.length() - 1, s.length());
        }
    }
    /**
     * 找出所有子集的异或总和再求和
     */
    int retSubsetXORSum;
    int nSubsetXORSum;
    public int subsetXORSum(int[] nums) {
        nSubsetXORSum = nums.length;
        retSubsetXORSum = 0;
        dfs(nums, 0, 0);
        return retSubsetXORSum;
    }

    void dfs(int[] nums, int i, int cur){
        for(int j = i; j < nSubsetXORSum; j++){
            int v = cur ^ nums[j];
            retSubsetXORSum += v;
            dfs(nums, j + 1, v);
        }
    }
    /**
     * 子集
     */
    List<List<Integer>> retSubsets;
    List<Integer> pathSubsets;
    int nSubsets;
    public List<List<Integer>> subsets(int[] nums) {
        nSubsets = nums.length;
        retSubsets = new LinkedList<>();
        pathSubsets = new LinkedList<>();
        dfs(nums, 0);
        return retSubsets;
    }
    void dfsSubsetsBe(int[] nums, int i){
        retSubsets.add(new LinkedList<>(pathSubsets));
        for(int j = i; j < nSubsets; j++){
            pathSubsets.add(nums[j]);
            dfsSubsetsBe(nums, j + 1);
            pathSubsets.remove(pathSubsets.size() - 1);
        }
    }
    //当前递归的元素
    void dfs(int[] nums, int i){
        if(i == nSubsets){
            retSubsets.add(new LinkedList<>(pathSubsets));
            return;
        }
        //i不选
        dfs(nums, i + 1);
        //选
        pathSubsets.add(nums[i]);
        dfs(nums, i + 1);
        pathSubsets.remove(pathSubsets.size() - 1);
    }
    /**
     * 全排列
     */


    int nPermute;
    boolean[] checkPermute;
    List<Integer> pathPermute;
    List<List<Integer>> retPermute;
    public List<List<Integer>> permute(int[] nums) {
        nPermute = nums.length;
        checkPermute = new boolean[nPermute];
        pathPermute = new LinkedList<>();
        retPermute = new LinkedList<>();
        dfs(nums);
        return retPermute;
    }

    void dfs(int[] nums){
        for(int i = 0; i < nPermute; i++){
            if(checkPermute[i]) continue;
            pathPermute.add(nums[i]);
            checkPermute[i] = true;
            if(pathPermute.size() == nPermute){
                retPermute.add(new LinkedList(pathPermute));
                pathPermute.remove(pathPermute.size() - 1);
                checkPermute[i] = false;
                return;
            }
            dfs(nums);

            pathPermute.remove(pathPermute.size() - 1);
            checkPermute[i] = false;
        }
    }

    /**
     * 二叉树的所有路径
     */
    List<String> retList;
    public List<String> binaryTreePaths(TreeNode root) {
        retList = new LinkedList<>();
        dfsBinaryTreePaths(root, new StringBuilder());
        return retList;
    }

    void dfsBinaryTreePaths(TreeNode node, StringBuilder s){
        StringBuilder news = (new StringBuilder(s)).append(node.val);
        if(node.left == null && node.right == null){
            retList.add(news.toString());
            return;
        }
        news.append("->");
        if(node.left != null) dfsBinaryTreePaths(node.left, news);
        if(node.right != null) dfsBinaryTreePaths(node.right, news);
    }

    /**
     * 二叉搜索树中第 K 小的元素
     */
    int iKthSmallest = 0;
    int retKthSmallest = 0;
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return retKthSmallest;
    }

    void dfs(TreeNode root,int k){
        if(root == null || iKthSmallest == k) return;
        dfs(root.left, k);
        iKthSmallest++;
        if(iKthSmallest == k) retKthSmallest = root.val;
        dfs(root.right, k);
    }
    /**
     * 验证二叉搜索树
     */
    long prev;
    boolean flg;
    public boolean isValidBST(TreeNode root) {
        prev = Long.MIN_VALUE;
        flg = true;
        dfsIsValidBST(root);
        return flg;
    }

    void dfsIsValidBST(TreeNode root){
        if(!flg) return;

        if(root == null) return;

        dfs(root.left);

        if(prev >= root.val) flg = false;

        prev = root.val;

        dfs(root.right);
    }
    /**
     * 二叉树剪枝
     */
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;

        TreeNode left = pruneTree(root.left);
        TreeNode right = pruneTree(root.right);

        if(left == null && right == null && root.val == 0) return null;

        root.left = left;
        root.right = right;
        return root;
    }

    /**
     * 求根节点到叶节点数字之和
     */
    int retSumNumbers = 0;
    public int sumNumbers(TreeNode root) {
        dfsSumNumbers(root, new StringBuilder());
        return retSumNumbers;
    }

    //要知道每条路 先序遍历
    //曲线救国
    void dfsSumNumbers(TreeNode node, StringBuilder v) {
        v.append(node.val);
        if (node.left == null && node.right == null) {
            retSumNumbers += Integer.parseInt(v.toString());
            return;
        }
        if (node.left != null)
            dfsSumNumbers(node.left, new StringBuilder(v));
        if (node.right != null)
            dfsSumNumbers(node.right, new StringBuilder(v));
    }

    /**
     * 计算布尔二叉树的值
     * 中序遍历
     */
    public boolean evaluateTree(TreeNode root) {
        return dfs(root);
    }
    // 0 f  1 t  2 or  3 and
    boolean dfs(TreeNode node){
        if(node.left == null) return node.val == 0 ? false : true;

        boolean l =  dfs(node.left);
        boolean r =  dfs(node.right);
        return node.val == 2 ? l || r : l && r;
    }
    /**
     * 快速幂
     */
    public double myPow(double x, int n) {
        return n > 0 ? dfs(x, n) : 1 / dfs(x, -n);
    }

    double dfs(double x, int n){
        if(n == 0) return 1.0;
        double tmp = dfs(x, n / 2);
        return n % 2 == 0 ?  tmp * tmp : tmp * tmp * x;
    }
    /**
     * 反转链表
     */
    public ListNode reverseList(ListNode head) {
        return dfs(head);
    }

    ListNode dfs(ListNode node){
        if(node == null || node.next == null) return node;
        ListNode ret = dfs(node.next);
        node.next.next = node;
        node.next = null;
        return ret;
    }
    /**
     * 合并俩个有序数组
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ret = new ListNode();
        recursion(list1, list2, ret);
        return ret.next;
    }

    void recursion(ListNode list1, ListNode list2, ListNode cur) {
        if (list1 == null){
            cur.next = list2;
            return;
        }
        if(list2 == null){
            cur.next = list1;
            return;
        }
        if (list1.val < list2.val) {
            cur.next = list1;
            recursion(list1.next, list2, cur.next);
        } else {
            cur.next = list2;
            recursion(list1, list2.next, cur.next);
        }
    }
    /**
     * 汉诺塔
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }
    // n 将a的n个元素移动到c
    void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n){
        if(n == 1){
            C.add(A.remove(A.size() - 1));
            return;
        }

        dfs(A, C, B, n - 1);
        C.add(A.remove(A.size() - 1));
        //不适用b size是因为这n时表示的时抽象逻辑上的盘子的数目，而用b这个实际的数目来表示，会导致
        //实际移动的n偏小，且这个b的size式在运行中因为上一层代码的递归而改变，引起不可预料的变化
        dfs(B, A, C, n - 1);
    }
}
